package newcoder;

import java.util.Arrays;

/**
 * @Author 肖地洋
 * @Date 2022/7/14 17:33
 */
public class NC203 {

    int[] nums;
    int res;
    public static void main(String[] args) {
        NC203 nc203 = new NC203();
        int[] nu = {1,2,4,5};
        int res = nc203.change1(5,nu);
        System.out.println(res);
    }

    public int change (int target, int[] nums) {
        this.nums = nums;
        Arrays.sort(nums);
        dfs(target,0);
        return res;
    }

    public void dfs(int target, int id){
        if(nums[id]>target) return;
        for(int i=0;i<=target/nums[id];i++){
            if(target==i*nums[id]) res++;
            if(id<nums.length-1){
                dfs(target-i*nums[id],id+1);
            }
        }
    }

    public int change1 (int target, int[] nums) {
        int[] dp = new int[target+1];
        dp[0] = 1;
        for(int i = 0;i<nums.length;i++){
            for(int num = nums[i];num<=target;num++){
                dp[num]+=dp[num-nums[i]];
            }
        }
        return dp[target];
    }

}
